/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年04月14日
*   描
述：使用双指针，1号指针先走长度n+1，然后2号指针开始从头和1号指针一起走，1号指针走到链表结束时，2号指针指向结点的下一个结点刚好是要删除的结点。
*
================================================================*/

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
  int val;
  struct ListNode *next;
};

struct ListNode *removeNthFromEnd(struct ListNode *head, int n) {
  if (head == NULL) {
    return NULL;  // 处理空链表的情况
  }

  struct ListNode *fastPtr = head, *slowPtr = head;

  // 快指针先走 n 步，使快慢指针间隔为 n
  for (int i = 0; i < n && fastPtr != NULL; i++) {
    fastPtr = fastPtr->next;
  }

  // 如果 n 等于链表长度，则需要删除头节点
  if (fastPtr == NULL) {
    struct ListNode *newHead = head->next;
    free(head);
    return newHead;
  }

  // 快慢指针一起走，直到快指针到达尾部
  while (fastPtr->next != NULL) {
    fastPtr = fastPtr->next;
    slowPtr = slowPtr->next;
  }

  // 删除 slowPtr 的下一个节点（即倒数第 n 个节点）
  struct ListNode *toRemove = slowPtr->next;
  slowPtr->next = slowPtr->next->next;

  free(toRemove);

  return head;
}

// int main() {
//   struct ListNode *currNode = NULL;
//   struct ListNode *listA = (struct ListNode *)malloc(sizeof(struct
//   ListNode));

//   listA->val = 1;
//   listA->next = (struct ListNode *)malloc(sizeof(struct ListNode));
//   currNode = listA->next;

//   currNode->val = 2;
//   currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
//   currNode = currNode->next;

//   currNode->val = 3;
//   currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
//   currNode = currNode->next;

//   currNode->val = 4;
//   currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
//   currNode = currNode->next;

//   currNode->val = 5;
//   currNode->next = NULL;

//   removeNthFromEnd(listA, 5);
// }

int main() {
  struct ListNode *currNode = NULL;
  struct ListNode *listA = (struct ListNode *)malloc(sizeof(struct ListNode));

  listA->val = 1;
  listA->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = listA->next;

  currNode->val = 2;
  currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 3;
  currNode->next = NULL;

  removeNthFromEnd(listA, 2);
}
